/*
 * Copyright (c) Kumo Inc. and affiliates.
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Docs: https://fburl.com/fbcref_dynamic
// 1-minute video primer: https://www.youtube.com/watch?v=3XubaLCDYOM
//

/**
 * Dynamic is a runtime dynamically typed value.  It holds types from a specific
 * predetermined set of types: int, double, bool, nullptr_t, string, array,
 * map. In particular, it can be used as a convenient in-memory representation
 * for complete JSON objects.
 *
 * In general, Dynamic can be used as if it were the type it represents
 * (although in some cases with a slightly less complete interface than the raw
 * type). If there is a runtime type mismatch, then Dynamic will throw a
 * TypeError.
 *
 * See melon/json.h for serialization and deserialization functions for JSON.
 *
 * Additional documentation is in
 * https://github.com/facebook/melon/blob/main/melon/docs/Dynamic.md
 *
 * @refcode melon/docs/examples/melon/dynamic.cpp
 * @struct melon::Dynamic
 */
/*
 * Some examples:
 *
 *   Dynamic twelve = 12;
 *   Dynamic str = "string";
 *   Dynamic map = Dynamic::object;
 *   map[str] = twelve;
 *   map[str + "another_str"] = Dynamic::array("array", "of", 4, "elements");
 *   map.insert("null_element", nullptr);
 *   ++map[str];
 *   assert(map[str] == 13);
 *
 *   // Building a complex object with a sub array inline:
 *   Dynamic d = Dynamic::object
 *     ("key", "value")
 *     ("key2", Dynamic::array("a", "array"))
 *     ;
 */

#pragma once

#include <cstdint>
#include <memory>
#include <ostream>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include <melon/expected.h>
#include <melon/range.h>
#include <melon/traits.h>
#include <melon/container/f14_map.h>
#include <melon/json_pointer.h>

namespace melon {
    //////////////////////////////////////////////////////////////////////

    struct const_dynamic_view;
    struct Dynamic;
    struct dynamic_view;
    struct TypeError;

    //////////////////////////////////////////////////////////////////////

    namespace dynamic_detail {
        template<typename T>
        using detect_construct_string = decltype(std::string(
            MELON_DECLVAL(T const&).data(), MELON_DECLVAL(T const&).size()));
    }

    struct Dynamic {
        enum Type {
            NULLT,
            ARRAY,
            BOOL,
            DOUBLE,
            INT64,
            OBJECT,
            STRING,
        };

        template<class T, class Enable = void>
        struct NumericTypeHelper;

        /*
         * We support direct iteration of arrays, and indirect iteration of objects.
         * See begin(), end(), keys(), values(), and items() for more.
         *
         * Array iterators dereference as the elements in the array.
         * Object key iterators dereference as the keys in the object.
         * Object value iterators dereference as the values in the object.
         * Object item iterators dereference as pairs of (key, value).
         */
    private:
        typedef std::vector<Dynamic> Array;

        /*
         * Violating spec, std::vector<bool>::const_reference is not bool in libcpp:
         * http://howardhinnant.github.io/onvectorbool.html
         *
         * This is used to add a public ctor which is only enabled under libcpp taking
         * std::vector<bool>::const_reference without using the preprocessor.
         */
        struct VectorBoolConstRefFake : std::false_type {
        };

        using VectorBoolConstRefCtorType = std::conditional_t<
            std::is_same<std::vector<bool>::const_reference, bool>::value,
            VectorBoolConstRefFake,
            std::vector<bool>::const_reference>;

    public:
        typedef Array::iterator iterator;
        typedef Array::const_iterator const_iterator;
        typedef Dynamic value_type;

        struct const_key_iterator;
        struct const_value_iterator;
        struct const_item_iterator;

        struct value_iterator;
        struct item_iterator;

        /*
         * Creation routines for making Dynamic objects and arrays.  Objects
         * are maps from key to value (so named due to json-related origins
         * here).
         *
         * Example:
         *
         *   // Make a fairly complex Dynamic:
         *   Dynamic d = Dynamic::object("key", "value1")
         *                              ("key2", Dynamic::array("value",
         *                                                      "with",
         *                                                      4,
         *                                                      "words"));
         *
         *   // Build an object in a few steps:
         *   Dynamic d = Dynamic::object;
         *   d["key"] = 12;
         *   d["something_else"] = Dynamic::array(1, 2, 3, nullptr);
         */
    private:
        struct EmptyArrayTag {
        };

        struct ObjectMaker;

    public:
        /**
         * Do not use.
         *
         * @methodset Array
         */
        static void array(EmptyArrayTag);

        /**
         * @brief Construct a Dynamic array.
         *
         * Special syntax because `Dynamic d = { ... }` dispatches to the copy
         * constructor.
         * See D3013423 and
         * [DR95](http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1467).
         *
         * @refcode melon/docs/examples/melon/dynamic/array.cpp
         * @methodset Array
         */
        template<class... Args>
        static Dynamic array(Args &&... args);

        /**
         * Construct a Dynamic object.
         *
         * @refcode melon/docs/examples/melon/dynamic/object.cpp
         * @methodset Object
         */
        static ObjectMaker object();

        static ObjectMaker object(Dynamic, Dynamic);

        /**
         * Default constructor, initializes with nullptr.
         */
        Dynamic();

        /*
         * String compatibility constructors.
         */
        /// Initializes as an empty string.
        /* implicit */
        Dynamic(std::nullptr_t);

        /// Initializes with strcpy.
        /* implicit */
        Dynamic(char const *s);

        /// Initializes as a string.
        /* implicit */
        Dynamic(std::string s);

        /// Initializes as a string.
        template<
            typename Stringish,
            typename = std::enable_if_t<
                is_detected_v<dynamic_detail::detect_construct_string, Stringish> > >
        /* implicit */ Dynamic(Stringish &&s);

        /*
         * This is part of the plumbing for array() and object(), above.
         * Used to create a new array or object Dynamic.
         */
        /// Plumbing for array() construction.
        /* implicit */
        Dynamic(void (*)(EmptyArrayTag));

        /// Plumbing for object() construction.
        /* implicit */
        Dynamic(ObjectMaker (*)());

        /// Plumbing for object() construction.
        /* implicit */
        Dynamic(ObjectMaker const &) = delete;

        /// Plumbing for object() construction.
        /* implicit */
        Dynamic(ObjectMaker &&);

        /**
         * Constructor for integral and float types.
         * Other types are SFINAEd out with NumericTypeHelper.
         */
        template<class T, class NumericType = typename NumericTypeHelper<T>::type>
        /* implicit */ Dynamic(T t);

        /**
         * Special handling for vector<bool>.
         *
         * If v is vector<bool>, v[idx] is a proxy object implicitly convertible to
         * bool. Calling a function f(Dynamic) with f(v[idx]) would require a double
         * implicit conversion (reference -> bool -> Dynamic) which is not allowed,
         * hence we explicitly accept the reference proxy.
         */
        /* implicit */
        Dynamic(std::vector<bool>::reference b);

        /// Special handling for vector<bool>::const_reference.
        /* implicit */
        Dynamic(VectorBoolConstRefCtorType b);

        /**
         * Create a Dynamic that is an array of the values from the supplied
         * iterator range.
         */
        template<class Iterator>
        explicit Dynamic(Iterator first, Iterator last);

        Dynamic(Dynamic const &);

        Dynamic(Dynamic &&) noexcept;

        ~Dynamic() noexcept;

        /**
         * Deep equality comparison.  This will compare all the way down
         * an object or array, and is potentially expensive.
         *
         * NOTE: Implicit conversion will be done between ints and doubles, so numeric
         * equality will apply between those cases. Other Dynamic value comparisons of
         * different types will always return false.
         */
        friend bool operator==(Dynamic const &a, Dynamic const &b);

        friend bool operator!=(Dynamic const &a, Dynamic const &b) {
            return !(a == b);
        }

        /*
         * For all types except object this returns the natural ordering on
         * those types.  For objects, we throw TypeError.
         *
         * NOTE: Implicit conversion will be done between ints and doubles, so numeric
         * ordering will apply between those cases. Other Dynamic value comparisons of
         * different types will maintain consistent ordering within a binary run.
         */
        friend bool operator<(Dynamic const &a, Dynamic const &b);

        friend bool operator>(Dynamic const &a, Dynamic const &b) { return b < a; }

        friend bool operator<=(Dynamic const &a, Dynamic const &b) {
            return !(b < a);
        }

        friend bool operator>=(Dynamic const &a, Dynamic const &b) {
            return !(a < b);
        }

        /*
         * General operators.
         *
         * These throw TypeError when used with types or type combinations
         * that don't support them.
         *
         * These functions may also throw if you use 64-bit integers with
         * doubles when the integers are too big to fit in a double.
         */
        /// @methodset Op
        Dynamic &operator+=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator-=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator*=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator/=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator%=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator|=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator&=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator^=(Dynamic const &);

        /// @methodset Op
        Dynamic &operator++();

        /// @methodset Op
        Dynamic &operator--();

        friend Dynamic operator+(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) += b);
        }

        friend Dynamic operator-(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) -= b);
        }

        friend Dynamic operator*(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) *= b);
        }

        friend Dynamic operator/(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) /= b);
        }

        friend Dynamic operator%(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) %= b);
        }

        friend Dynamic operator|(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) |= b);
        }

        friend Dynamic operator&(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) &= b);
        }

        friend Dynamic operator^(Dynamic const &a, Dynamic const &b) {
            return std::move(copy(a) ^= b);
        }

        friend Dynamic operator+(Dynamic &&a, Dynamic const &b) {
            return std::move(a += b);
        }

        /// @methodset Op
        Dynamic operator++(int) {
            auto self = *this;
            return ++*this, self;
        }

        /// @methodset Op
        Dynamic operator--(int) {
            auto self = *this;
            return --*this, self;
        }

        /**
         * Assignment from other dynamics.
         *
         * Because of the implicit conversion to Dynamic from its potential types, you
         * can use this to change the type pretty intuitively.
         *
         * Basic guarantee only.
         */
        Dynamic &operator=(Dynamic const &);

        Dynamic &operator=(Dynamic &&) noexcept;

        /*
         * Minor performance optimization: allow assignment from cheap
         * primitive types without creating a temporary Dynamic.
         */
        template<class T, class NumericType = typename NumericTypeHelper<T>::type>
        Dynamic &operator=(T t);

        Dynamic &operator=(std::nullptr_t);

        /*
         * For simple dynamics (not arrays or objects), this prints the
         * value to an std::ostream in the expected way.  Respects the
         * formatting manipulators that have been sent to the stream
         * already.
         *
         * If the Dynamic holds an object or array, this prints them in a
         * format very similar to JSON.  (It will in fact actually be JSON
         * as long as the Dynamic validly represents a JSON object---i.e. it
         * can't have non-string keys.)
         */
        friend std::ostream &operator<<(std::ostream &, Dynamic const &);

        /**
         * @brief Type test.
         *
         * Returns true if this Dynamic is of the specified type.
         *
         * @methodset Typing
         */
        [[nodiscard]] bool isString() const;

        /// @copydoc isString
        [[nodiscard]] bool isObject() const;

        /// @copydoc isString
        [[nodiscard]] bool isBool() const;

        /// @copydoc isString
        [[nodiscard]] bool isNull() const;

        /// @copydoc isString
        [[nodiscard]] bool isArray() const;

        /// @copydoc isString
        [[nodiscard]] bool isDouble() const;

        /// @copydoc isString
        [[nodiscard]] bool isInt() const;

        /**
         * @copydoc isString
         *
         * @return `isInt() || isDouble()`.
         */
        [[nodiscard]] bool isNumber() const;

        /**
         * The type of this Dynamic.
         *
         * @methodset Typing
         */
        [[nodiscard]] Type type() const;

        /**
         * The type of this Dynamic as a printable string.
         *
         * @methodset Typing
         */
        const char *typeName() const;

        /**
         * Type conversion.
         *
         * Extract a value while trying to convert to the specified type.
         * Throws exceptions if we cannot convert from the real type to the
         * requested type.
         *
         * C++ will implicitly convert between bools, ints, and doubles; these
         * conversion functions also try to convert between arithmetic types and
         * strings. E.g. Dynamic d = "12"; d.asDouble() -> 12.0.
         *
         * Note: you can only use this to access integral types or strings,
         * since arrays and objects are generally best dealt with as a
         * Dynamic.
         *
         * @methodset Conversion
         */
        [[nodiscard]] std::string asString() const;

        /// @copydoc asString
        [[nodiscard]] double asDouble() const;

        /// @copydoc asString
        [[nodiscard]] int64_t asInt() const;

        /// @copydoc asString
        [[nodiscard]] bool asBool() const;

        /**
         * Type extraction.
         *
         * Extract the value stored in this Dynamic without type conversion.
         *
         * These will throw a TypeError if the Dynamic has a different type.
         *
         * @methodset Extraction
         */
        [[nodiscard]] const std::string &getString() const &;

        /// @copydoc getString
        [[nodiscard]] double getDouble() const &;

        /// @copydoc getString
        [[nodiscard]] int64_t getInt() const &;

        /// @copydoc getString
        [[nodiscard]] bool getBool() const &;

        std::string &getString() &;

        double &getDouble() &;

        int64_t &getInt() &;

        bool &getBool() &;

        std::string &&getString() &&;

        double getDouble() &&;

        int64_t getInt() &&;

        bool getBool() &&;

        /**
         * Get the c_str pointer.
         *
         * It is occasionally useful to access a string's internal pointer
         * directly, without the type conversion of `asString()`.
         *
         * These will throw a TypeError if the Dynamic is not a string.
         *
         * @methodset Extraction
         */
        [[nodiscard]] const char *c_str() const &;

        const char *c_str() && = delete;

        /// @copydoc c_str
        [[nodiscard]] StringPiece stringPiece() const;

        /**
         * Tests for emptiness.
         *
         * Returns: true if this Dynamic is null, an empty array, an empty
         * object, or an empty string.
         *
         * @methodset Container
         */
       [[nodiscard]] bool empty() const;

        /**
         * Get size.
         *
         * If this is an array or an object, returns the number of elements
         * contained.  If it is a string, returns the length.  Otherwise
         * throws TypeError.
         *
         * @methodset Container
         */
       [[nodiscard]] std::size_t size() const;

        /**
         * Array iteration.
         *
         * You can iterate over the values of the array.  Calling these on
         * non-arrays will throw a TypeError.
         *
         * @methodset Iteration
         */
      [[nodiscard]]  const_iterator begin() const;

        /// @copydoc begin
       [[nodiscard]] const_iterator end() const;

        iterator begin();

        iterator end();

    private:
        /*
         * Helper object returned by keys(), values(), and items().
         */
        template<class T>
        struct IterableProxy;

        /*
         * Helper for heterogeneous lookup and mutation on objects: at(), find(),
         * count(), erase(), operator[]
         */
        template<typename K, typename T>
        using IfIsNonStringDynamicConvertible = std::enable_if_t<
            !std::is_convertible<K, StringPiece>::value &&
            std::is_convertible<K, Dynamic>::value,
            T>;

        template<typename K, typename T>
        using IfNotIterator =
        std::enable_if_t<!std::is_convertible<K, iterator>::value, T>;

    public:
        /*
         * You can iterate over the keys, values, or items (std::pair of key and
         * value) in an object.  Calling these on non-objects will throw a TypeError.
         */
        /**
         * Get the keys of an object.
         *
         * Return an iterable interface for the object's keys.
         *
         * @methodset Iteration
         */
       [[nodiscard]] IterableProxy<const_key_iterator> keys() const;

        /**
         * Get the values of an object.
         *
         * Return an iterable interface for the object's values, without their
         * associated key.
         *
         * @methodset Iteration
         */
       [[nodiscard]] IterableProxy<const_value_iterator> values() const;

        /**
         * Get key-value items of an object.
         *
         * Return an iterable interface for the object's key-value pairs.
         * The type of this iterable is `(const Dynamic&, Dynamic&)`.
         *
         * @methodset Iteration
         */
       [[nodiscard]] IterableProxy<const_item_iterator> items() const;

        IterableProxy<value_iterator> values();

        IterableProxy<item_iterator> items();

        /**
         * Find by key.
         *
         * AssociativeContainer-style find interface for objects.  Throws if
         * this is not an object.
         *
         * @return items().end() if the key is not present, or a
         * const_item_iterator pointing to the item.
         *
         * @methodset Object
         */
        template<typename K>
        IfIsNonStringDynamicConvertible<K, const_item_iterator> find(K &&) const;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, item_iterator> find(K &&);

       [[nodiscard]] const_item_iterator find(StringPiece) const;

        item_iterator find(StringPiece);

        /**
         * Count by key.
         *
         * If this is an object, returns whether it contains a field with
         * the given name.  Otherwise throws TypeError.
         *
         * @methodset Object
         */
        template<typename K>
        IfIsNonStringDynamicConvertible<K, std::size_t> count(K &&) const;

        [[nodiscard]] std::size_t count(StringPiece) const;

    private:
       [[nodiscard]] Dynamic const &atImpl(Dynamic const &) const &;

    public:
        /**
         * Access sub-field or index.
         *
         * For objects or arrays, provides access to sub-fields by index or
         * field name.
         *
         * Using these with Dynamic objects that are not arrays or objects
         * will throw a TypeError.  Using an index that is out of range or
         * object-element that's not present throws std::out_of_range.
         *
         * @methodset Element access
         */
        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic const &> at(K &&) const &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic &> at(K &&) &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic &&> at(K &&) &&;

       [[nodiscard]] Dynamic const &at(StringPiece) const &;

        Dynamic &at(StringPiece) &;

        Dynamic &&at(StringPiece) &&;

        /*
         * Locate element using JSON pointer, per RFC 6901
         */

        enum class json_pointer_resolution_error_code : uint8_t {
            other = 0,
            // key not found in object
            key_not_found,
            // array index out of bounds
            index_out_of_bounds,
            // special index "-" requesting append
            append_requested,
            // indexes in arrays must be numeric
            index_not_numeric,
            // indexes in arrays should not have leading zero
            index_has_leading_zero,
            // element not subscribable, i.e. neither object or array
            element_not_object_or_array,
            // hit document boundary, but pointer not exhausted yet
            json_pointer_out_of_bounds,
        };

        template<typename Dynamic>
        struct json_pointer_resolution_error {
            // error code encountered while resolving JSON pointer
            json_pointer_resolution_error_code error_code{};
            // index of the JSON pointer's token that caused the error
            size_t index{0};
            // Last correctly resolved element in object. You can use it,
            // for example, to add last element to the array
            Dynamic *context{nullptr};
        };

        template<typename Dynamic>
        struct json_pointer_resolved_value {
            // parent element of the value in Dynamic, if exist
            Dynamic *parent{nullptr};
            // pointer to the value itself
            Dynamic *value{nullptr};
            // if parent isObject, this is the key in object to get value
            StringPiece parent_key;
            // if parent isArray, this is the index in array to get value
            size_t parent_index{0};
        };

  // clang-format off
  template <typename Dynamic>
  using resolved_json_pointer = Expected<
      json_pointer_resolved_value<Dynamic>,
      json_pointer_resolution_error<Dynamic>>;

  /**
   * Get JSON Pointer.
   *
   * See [Relative JSON Pointers RFC 6901](https://json-schema.org/draft/2019-09/relative-json-pointer.html)
   *
   * @methodset Element access
   */
 [[nodiscard]] resolved_json_pointer<Dynamic const>
  try_get_ptr(json_pointer const&) const&;
  resolved_json_pointer<Dynamic>
  try_get_ptr(json_pointer const&) &;
 [[nodiscard]] resolved_json_pointer<Dynamic const>
  try_get_ptr(json_pointer const&) const&& = delete;
  resolved_json_pointer<Dynamic const>
  try_get_ptr(json_pointer const&) && = delete;
        // clang-format on

        /**
         * Nullable access.
         *
         * Like `at` (for objects and arrays) and `try_get_ptr` (for json_pointer
         * lookup), but returns nullptr if the element cannot be found instead of
         * throwing a TypeError.
         *
         * For the JSON Pointer overloads, throws if pointer does not match the shape
         * of the document, e.g. uses string to index in array.
         *
         * @methodset Element access
         */
       [[nodiscard]] const Dynamic *get_ptr(json_pointer const &) const &;

        Dynamic *get_ptr(json_pointer const &) &;

       [[nodiscard]] const Dynamic *get_ptr(json_pointer const &) const && = delete;

        Dynamic *get_ptr(json_pointer const &) && = delete;

    private:
       [[nodiscard]] const Dynamic *get_ptrImpl(Dynamic const &) const &;

    public:
        /*
         * Like 'at', above, except it returns either a pointer to the contained
         * object or nullptr if it wasn't found. This allows a key to be tested for
         * containment and retrieved in one operation. Example:
         *
         *   if (auto* found = d.get_ptr(key))
         *     // use *found;
         *
         * Using these with Dynamic objects that are not arrays or objects
         * will throw a TypeError.
         */
        template<typename K>
        IfIsNonStringDynamicConvertible<K, const Dynamic *> get_ptr(K &&) const &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic *> get_ptr(K &&) &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic *> get_ptr(K &&) && = delete;

       [[nodiscard]] const Dynamic *get_ptr(StringPiece) const &;

        Dynamic *get_ptr(StringPiece) &;

        Dynamic *get_ptr(StringPiece) && = delete;

        /**
         * Element lookup.
         *
         * This works for access to both objects and arrays.
         *
         * In the case of an array, the index must be an integer, and this
         * will throw std::out_of_range if it is less than zero or greater
         * than size().
         *
         * In the case of an object, the non-const overload inserts a null
         * value if the key isn't present.  The const overload will throw
         * std::out_of_range if the key is not present.
         *
         * These functions do not invalidate iterators except when a null value
         * is inserted into an object as described above.
         *
         * @methodset Element access
         */
        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic &> operator[](K &&) &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic const &> operator[](K &&) const &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic &&> operator[](K &&) &&;

        Dynamic &operator[](StringPiece) &;

        Dynamic const &operator[](StringPiece) const &;

        Dynamic &&operator[](StringPiece) &&;

        /**
         * Defaulted lookup.
         *
         * getDefault will return the value associated with the supplied key, the
         * supplied default otherwise.
         *
         * Only defined for objects, throws TypeError otherwise.
         *
         * @methodset Object
         */
        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic> getDefault(
            K &&k, const Dynamic &v = Dynamic::object) const &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic> getDefault(
            K &&k, Dynamic &&v) const &;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic> getDefault(
            K &&k, const Dynamic &v = Dynamic::object) &&;

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic> getDefault(K &&k, Dynamic &&v) &&;

       [[nodiscard]] Dynamic getDefault(StringPiece k, const Dynamic &v = Dynamic::object) const &;

        Dynamic getDefault(StringPiece k, Dynamic &&v) const &;

        Dynamic getDefault(StringPiece k, const Dynamic &v = Dynamic::object) &&;

        Dynamic getDefault(StringPiece k, Dynamic &&v) &&;

        /**
         * Maybe set.
         *
         * setDefault will set the key to the supplied default if it is not yet set,
         * otherwise leaving it. setDefault returns a reference to the existing value
         * if present, the new value otherwise.
         *
         * Only defined for objects, throws TypeError otherwise.
         *
         * @methodset Object
         */
        template<typename K, typename V>
        IfIsNonStringDynamicConvertible<K, Dynamic &> setDefault(K &&k, V &&v);

        template<typename V>
        Dynamic &setDefault(StringPiece k, V &&v);

        // MSVC 2015 Update 3 needs these extra overloads because if V were a
        // defaulted template parameter, it causes MSVC to consider v an rvalue
        // reference rather than a universal reference, resulting in it not being
        // able to find the correct overload to construct a Dynamic with.
        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic &> setDefault(K &&k, Dynamic &&v);

        template<typename K>
        IfIsNonStringDynamicConvertible<K, Dynamic &> setDefault(
            K &&k, const Dynamic &v = Dynamic::object);

        Dynamic &setDefault(StringPiece k, Dynamic &&v);

        Dynamic &setDefault(StringPiece k, const Dynamic &v = Dynamic::object);

        /**
         * Change size.
         *
         * Resizes an array so it has at n elements, using the supplied
         * default to fill new elements.  Throws TypeError if this Dynamic
         * is not an array.
         *
         * May invalidate iterators.
         *
         * Post: size() == n
         *
         * @methodset Array
         */
        void resize(std::size_t sz, Dynamic const & = nullptr);

        /**
         * Pre-allocate size.
         *
         * If this is an array, an object, or a string, reserves the requested
         * capacity in the underlying container.  Otherwise throws TypeError.
         *
         * May invalidate iterators, and does not give any additional guarantees on
         * iterator invalidation on subsequent insertions; the only purpose is for
         * optimization.
         *
         * @methodset Container
         */
        void reserve(std::size_t capacity);

        /**
         * @brief Overwriting insertion.
         *
         * Inserts the supplied key-value pair to an object, or throws if
         * it's not an object. If the key already exists, insert will overwrite the
         * value, i.e., similar to insert_or_assign.
         *
         * Invalidates iterators.
         *
         * @methodset Container
         */
        template<class K, class V>
        IfNotIterator<K, void> insert(K &&, V &&val);

        /**
         * Overwriting emplacement.
         *
         * Inserts an element into an object constructed in-place with the given args
         * if there is no existing element with the key, or throws if it's not an
         * object. Returns a pair consisting of an iterator to the inserted element,
         * or the already existing element if no insertion happened, and a bool
         * denoting whether the insertion took place.
         *
         * Invalidates iterators.
         *
         * @methodset Object
         */
        template<class... Args>
        std::pair<item_iterator, bool> emplace(Args &&... args);

        /**
         * Non-overwriting emplacement.
         *
         * Inserts an element into an object with the given key and value constructed
         * in-place with the given args if there is no existing element with the key,
         * or throws if it's not an object. Returns a pair consisting of an iterator
         * to the inserted element, or the already existing element if no insertion
         * happened, and a bool denoting whether the insertion took place.
         *
         * Invalidates iterators.
         *
         * @methodset Object
         */
        template<class K, class... Args>
        std::pair<item_iterator, bool> try_emplace(K &&key, Args &&... args);

        /**
         * Inserts the supplied value into array, or throw if not array.
         * Shifts existing values in the array to the right.
         *
         * Invalidates iterators.
         */
        template<class T>
        iterator insert(const_iterator pos, T &&value);

        /**
         * Inserts elements from range [first, last) before pos into an array.
         * Throws if the type is not an array.
         *
         * Invalidates iterators.
         */
        template<class InputIt>
        iterator insert(const_iterator pos, InputIt first, InputIt last);

        /**
         * Merge objects.
         *
         * Merge two melon Dynamic objects.
         * The "update" and "update_missing" functions extend the object by
         *  inserting the key/value pairs of mergeObj into the current object.
         *  For update, if key is duplicated between the two objects, it
         *  will overwrite with the value of the object being inserted (mergeObj).
         *  For "update_missing", it will prefer the value in the original object
         *
         * The "merge" function creates a new object consisting of the key/value
         * pairs of both mergeObj1 and mergeObj2
         * If the key is duplicated between the two objects,
         *  it will prefer value in the second object (mergeObj2)
         *
         * @methodset Object
         */
        void update(const Dynamic &mergeObj);

        /// @copydoc update
        void update_missing(const Dynamic &mergeObj1);

        /// @copydoc update
        static Dynamic merge(const Dynamic &mergeObj1, const Dynamic &mergeObj2);

        /**
         * Merge JSON Patch.
         *
         * Implement recursive version of RFC7386: JSON merge patch. This modifies
         * the current object.
         *
         * @methodset Object
         */
        void merge_patch(const Dynamic &patch);

        /**
         * Compute patch.
         *
         * Computes JSON merge patch (RFC7386) needed to mutate from source to target
         *
         * @methodset Object
         */
        static Dynamic merge_diff(const Dynamic &source, const Dynamic &target);

        /**
         * @brief Erases elements
         *
         * Erase an element from a Dynamic object, by key.
         *
         * Invalidates iterators to the element being erased.
         *
         * Returns the number of elements erased (i.e. 1 or 0).
         *
         * @methodset Container
         */
        template<typename K>
        IfIsNonStringDynamicConvertible<K, std::size_t> erase(K &&);

        std::size_t erase(StringPiece);

        /**
         * @brief Erases elements
         *
         * Erase an element from a Dynamic object or array, using an
         * iterator or an iterator range.
         *
         * In arrays, invalidates iterators to elements after the element
         * being erased.  In objects, invalidates iterators to the elements
         * being erased.
         *
         * Returns a new iterator to the first element beyond any elements
         * removed, or end() if there are none.  (The iteration order does
         * not change.)
         *
         * @methodset Container
         */
        iterator erase(const_iterator it);

        iterator erase(const_iterator first, const_iterator last);

        const_key_iterator erase(const_key_iterator it);

        const_key_iterator erase(const_key_iterator first, const_key_iterator last);

        value_iterator erase(const_value_iterator it);

        value_iterator erase(const_value_iterator first, const_value_iterator last);

        item_iterator erase(const_item_iterator it);

        item_iterator erase(const_item_iterator first, const_item_iterator last);

        /**
         * Append elements to an array.
         *
         * If this is not an array, throws TypeError.
         *
         * Invalidates iterators.
         *
         * @methodset Array
         */
        void push_back(Dynamic const &);

        void push_back(Dynamic &&);

        /**
         * Remove an element from the back of an array.
         *
         * If this is not an array, throws TypeError.
         *
         * Does not invalidate iterators.
         *
         * @methodset Array
         */
        void pop_back();

        /**
         * Return reference to the last element in an array.
         *
         * If this is not an array, throws TypeError.
         *
         * @methodset Array
         */
      [[nodiscard]]  const Dynamic &back() const;

        /**
         * Hash self.
         *
         * Get a hash code.  This function is called by a std::hash<>
         * specialization.
         *
         * Note: an int64_t and double will both produce the same hash if they are
         * numerically equal before rounding. So the int64_t 2 will have the same hash
         * as the double 2.0. But no double will intentionally hash to the hash of a
         * value that only when rounded will compare as equal. E.g. No double will
         * intentionally hash to the hash of INT64_MAX (2^63 - 1) given that a double
         * cannot represent this value.
         */
       [[nodiscard]] std::size_t hash() const;

    private:
        friend struct const_dynamic_view;
        friend struct dynamic_view;
        friend struct TypeError;
        struct ObjectImpl;
        template<class T>
        struct TypeInfo;
        template<class T>
        struct CompareOp;
        template<class T>
        struct GetAddrImpl;
        template<class T>
        struct PrintImpl;

        explicit Dynamic(Array &&r);

        template<class T>
        T const &get() const;

        template<class T>
        T &get();

        template<class T>
        T *get_nothrow() & noexcept;

        template<class T>
        T const *get_nothrow() const & noexcept;

        template<class T>
        T *get_nothrow() && noexcept = delete;

        template<class T>
        T *getAddress() noexcept;

        template<class T>
        T const *getAddress() const noexcept;

        template<class T>
        T asImpl() const;

        static char const *typeName(Type);

        // NOTE: like ~Dynamic, destroy() leaves type_ and u_ in an invalid state.
        void destroy() noexcept;

        void print(std::ostream &) const;

        void print_as_pseudo_json(std::ostream &) const; // see json.cpp

    private:
        Type type_;

        union Data {
            explicit Data() : nul(nullptr) {
            }

            ~Data() {
            }

            std::nullptr_t nul;
            Array array;
            bool boolean;
            double doubl;
            int64_t integer;
            std::string string;

            /*
             * Objects are placement new'd here.  We have to use a char buffer
             * because we don't know the type here (F14NodeMap<> with
             * Dynamic would be parameterizing a std:: template with an
             * incomplete type right now).  (Note that in contrast we know it
             * is ok to do this with kmvector because we own it.)
             */
            aligned_storage_for_t<F14NodeMap<int, int> > objectBuffer;
        } u_;
    };

    //////////////////////////////////////////////////////////////////////

    /**
     * This is a helper class for traversing an instance of Dynamic and accessing
     * the values within without risking throwing an exception. The primary use case
     * is to help write cleaner code when using dynamic instances without strict
     * schemas - eg. where keys may be missing, or Dynamic but with null values,
     * when expecting non-null values.
     *
     * Some examples:
     *
     *   Dynamic twelve = 12;
     *   Dynamic str = "string";
     *   Dynamic map = Dynamic::object("str", str)("twelve", 12);
     *
     *   dynamic_view view{map};
     *   assert(view.descend("str").string_or("bad") == "string");
     *   assert(view.descend("twelve").int_or(-1) == 12);
     *   assert(view.descend("zzz").string_or("aaa") == "aaa");
     *
     *   Dynamic wrapper = Dynamic::object("child", map);
     *   dynamic_view wrapper_view{wrapper};
     *
     *   assert(wrapper_view.descend("child", "str").string_or("bad") == "string");
     *   assert(wrapper_view.descend("wrong", 0, "huh").value_or(nullptr).isNull());
     */
    struct const_dynamic_view {
        // Empty view.
        const_dynamic_view() noexcept = default;

        // Basic view constructor. Creates a view of the referenced Dynamic.
        /* implicit */
        const_dynamic_view(Dynamic const &d) noexcept;

        const_dynamic_view(const_dynamic_view const &) noexcept = default;

        const_dynamic_view &operator=(const_dynamic_view const &) noexcept = default;

        // Allow conversion from mutable to immutable view.
        /* implicit */
        const_dynamic_view(dynamic_view &view) noexcept;

        /* implicit */
        const_dynamic_view &operator=(dynamic_view &view) noexcept;

        // Never view a temporary.
        explicit const_dynamic_view(Dynamic &&) = delete;

        // Returns true if this view is backed by a valid Dynamic, false otherwise.
        explicit operator bool() const noexcept;

        // Returns true if this view is not backed by a Dynamic, false otherwise.
        bool empty() const noexcept;

        // Resets the view to a default constructed state not backed by any Dynamic.
        void reset() noexcept;

        // Traverse a Dynamic by repeatedly applying operator[].
        // If all keys are valid, then the returned view will be backed by the
        // accessed Dynamic, otherwise it will be empty.
        template<typename Key, typename... Keys>
        const_dynamic_view descend(
            Key const &key, Keys const &... keys) const noexcept;

        // Untyped accessor. Returns a copy of the viewed Dynamic, or the default
        // value given if this view is empty, or a null Dynamic otherwise.
        Dynamic value_or(Dynamic &&val = nullptr) const;

        // The following accessors provide a read-only exception-safe API for
        // accessing the underlying viewed Dynamic. Unlike the main Dynamic APIs,
        // these follow a stricter contract, which also requires a caller-provided
        // default argument.
        //  - TypeError will not be thrown. primitive accessors further are marked
        //    noexcept.
        //  - No type conversions are performed. If the viewed Dynamic does not match
        //    the requested type, the default argument is returned instead.
        //  - If the view is empty, the default argument is returned instead.
        std::string string_or(char const *val) const;

       [[nodiscard]] std::string string_or(std::string val) const;

        template<
            typename Stringish,
            typename = std::enable_if_t<
                is_detected_v<dynamic_detail::detect_construct_string, Stringish> > >
        std::string string_or(Stringish &&val) const;

        double double_or(double val) const noexcept;

        int64_t int_or(int64_t val) const noexcept;

        bool bool_or(bool val) const noexcept;

    protected:
        /* implicit */
        const_dynamic_view(Dynamic const *d) noexcept;

        template<typename Key1, typename Key2, typename... Keys>
        Dynamic const *descend_(
            Key1 const &key1, Key2 const &key2, Keys const &... keys) const noexcept;

        template<typename Key>
        Dynamic const *descend_(Key const &key) const noexcept;

        template<typename Key>
        Dynamic::IfIsNonStringDynamicConvertible<Key, Dynamic const *>
        descend_unchecked_(Key const &key) const noexcept;

        Dynamic const *descend_unchecked_(StringPiece key) const noexcept;

        Dynamic const *d_ = nullptr;

        // Internal helper method for accessing a value by a type.
        template<typename T, typename... Args>
        T get_copy(Args &&... args) const;
    };

    struct dynamic_view : public const_dynamic_view {
        // Empty view.
        dynamic_view() noexcept = default;

        // dynamic_view can be used to view non-const dynamics only.
        /* implicit */
        dynamic_view(Dynamic &d) noexcept;

        dynamic_view(dynamic_view const &) noexcept = default;

        dynamic_view &operator=(dynamic_view const &) noexcept = default;

        // dynamic_view can not view const dynamics.
        explicit dynamic_view(Dynamic const &) = delete;

        // dynamic_view can not be initialized from a const_dynamic_view
        explicit dynamic_view(const_dynamic_view const &) = delete;

        // Like const_dynamic_view, but returns a dynamic_view.
        template<typename Key, typename... Keys>
        dynamic_view descend(Key const &key, Keys const &... keys) const noexcept;

        // dynamic_view provides APIs which can mutably access the backed Dynamic.
        // 'mutably access' in this case means extracting the viewed Dynamic or
        // value to omit unnecessary copies. It does not mean writing through to
        // the backed Dynamic - this is still just a view, not a mutator.

        // Moves the viewed Dynamic into the returned value via std::move. If the view
        // is not backed by a Dynamic, returns a provided default, or a null Dynamic.
        // Postconditions for the backed Dynamic are the same as for any Dynamic that
        // is moved-from. this->empty() == false.
        Dynamic move_value_or(Dynamic &&val = nullptr) noexcept;

        // Specific optimization for strings which can allocate, unlike the other
        // scalar types. If the viewed Dynamic is a string, the string value is
        // std::move'd to initialize a new instance which is returned.
        std::string move_string_or(std::string val) noexcept;

        std::string move_string_or(char const *val);

        template<
            typename Stringish,
            typename = std::enable_if_t<
                is_detected_v<dynamic_detail::detect_construct_string, Stringish> > >
        std::string move_string_or(Stringish &&val);

    private:
        template<typename T, typename... Args>
        T get_move(Args &&... args);
    };

    // A helper method which returns a contextually-correct dynamic_view for the
    // given view. If passed a Dynamic const&, returns a const_dynamic_view, and
    // if passed a Dynamic&, returns a dynamic_view.
    inline auto make_dynamic_view(Dynamic const &d) {
        return const_dynamic_view{d};
    }

    inline auto make_dynamic_view(Dynamic &d) {
        return dynamic_view{d};
    }

    auto make_dynamic_view(Dynamic &&) = delete;

    //////////////////////////////////////////////////////////////////////
} // namespace melon

namespace std {
    template<>
    struct hash<::melon::Dynamic> {
        using melon_is_avalanching = std::true_type;

        size_t operator()(::melon::Dynamic const &d) const { return d.hash(); }
    };
} // namespace std

#include <melon/json/dynamic-inl.h>
